#include <cstdio>
#include <cstring>
#include <queue>

typedef long long ll;
constexpr int N = 505, inf = 0x3f3f3f3f;
ll ans;
int n, m;
int indexl[N], indexr[N], slack[N], lmatch[N], rmatch[N], pre[N], map[N][N];
bool lvis[N], rvis[N];

inline void aug(int x) {
  static int tmp;
  while (x) {
    tmp = lmatch[pre[x]];
    rmatch[x] = pre[x];
    lmatch[rmatch[x]] = x;
    x = tmp;
  }
}

inline void bfsKM(int s) {
  static int d = inf;
  memset(lvis, 0, sizeof(lvis));
  memset(rvis, 0, sizeof(rvis));
  memset(slack, 0x3f, sizeof(slack));
  std::queue<int> q;
  q.push(s);
  while (true) {
    while (!q.empty()) {
      int u = q.front();
      q.pop(), lvis[u] = true;
      for (int v = 1; v <= n; ++v)
        if (!rvis[v]) {
          d = indexl[u] + indexr[v] - map[u][v];
          if (!d) {
            pre[v] = u;
            rvis[v] = true;
            if (!rmatch[v]) return aug(v);
            q.push(rmatch[v]);
          } else if (slack[v] > d)
            slack[v] = d, pre[v] = u;
        }
    }
    d = inf;
    for (int i = 1; i <= n; ++i)
      if (!rvis[i]) d = std::min(d, slack[i]);
    for (int i = 1; i <= n; ++i) {
      if (lvis[i]) indexl[i] -= d;
      if (rvis[i]) indexr[i] += d;
      else
        slack[i] -= d;
    }
    for (int i = 1; i <= n; ++i) {
      if (!rvis[i] && !slack[i]) {
        rvis[i] = true;
        if (!rmatch[i]) return aug(i);
        q.push(rmatch[i]);
      }
    }
  }
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("KM.in", "r", stdin);
  freopen("KM.out", "w", stdout);
#endif
#endif

  scanf("%d%d", &n, &m);
  memset(map, -0x3f, sizeof(map));
  for (int i = 1, y, c, h; i <= m; ++i) {
    scanf("%d%d%d", &y, &c, &h);
    map[y][c] = h;
  }
  memset(indexl, -0x3f, sizeof(indexl));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) indexl[i] = std::max(indexl[i], map[i][j]);
  for (int i = 1; i <= n; ++i) { bfsKM(i); }
  for (int i = 1; i <= n; ++i) ans += (long long)indexl[i] + indexr[i];
  printf("%lld\n", ans);
  for (int i = 1; i <= n; ++i) printf("%d ", rmatch[i]);
  return 0;
}